记一次面试 - huangjj27 的技术博客

总结一次面试

最值得总结的三个问题

有哪些方法？如何用这些方法实现一个 RwLock？

线程同步的目的在于解决多个线程访问关键资源时的竞争状态。一个数据竞争的简单例子如下：

use std::thread;
fn main() {
  let mut s = String::from("Hello");

  let thread1 = thread::spawn(|| {
    println!("{}", s);
  });

  let thread2 = thread::spawn(|| {
    s.push_str("World!");
    println!("{}", s);
  });

  thread1.join();
  thread2.join();
}

上文的代码中 thread1 试图打印 s, 预期得到输出 Hello, 但是 thread2 却改变了 s 的内容，那么 thread1 最终打印内容将取决于两个线程哪个先完成: 如果 thread1 先完成了，那么将打印 Hello; 如果 thread2 先完成了，那么将打印 HelloWorld!。

实际上得益于 Rust 的所有权系统与生命周期（lifetime）检查，上述示例并不能编译——子线程可能会在主程序结束后继续运行，导致子线程捕获的 s 的引用失效；另外 thread2 直接修改了 s ，换言之只会允许 thread2 独占地持有 s 的可变引用（ &mut s)，而不允许其他线程持有 s 的任何引用。

在 Rust 编程中，主要有以下线程同步的方法：

互斥锁 (Mutex) 我们可以使用互斥锁 Mutex<T> 来控制只能有单独一个线程读取/修改对象。通常实践是在外面加上原子引用计数 Arc 变成 Arc<Mutex<T>> ，来减少 Mutex 拷贝的开销。对于多读少写的场景，可以用 RwLock 提高并发。
条件变量 (CondVar) 条件变量用于 " 阻塞 " 线程并使得线程在等待事件时不需要消耗 CPU 时间。通常会与放进互斥锁布尔型的预言值（状态值）关联使用，在状态值发生变化时通知条件变量。
屏障 (Barrier) 屏障用于在某个需要若干线程 都完成 前置操作后再开始计算的操作之前，让所有所需线程的状态都达到能开始进行计算的状态。

有什么问题是生存期标注无法修正的？请给出一个例子

这道问题最后我也并没有理解，" 生命周期标注无法修正的问题 "，字面意思是，即使我们按照我们期望的程序语义来修正了生命周期标注，这个程序仍然不能通过编译，或者再运行时仍然不能得到期望结果。按此描述，一个可能的例子是，我们尝试从一个较短的引用返回一个较长的引用：

fn longhten<'a>(s_ref: &'a str) -> &'static str {
    s_ref
}

fn main() {
    let s = String::from("hello");

    let static_ref = longhten(&s);

    println!("{}", static_ref);
}

Waker 如何被唤醒？ Reactor 要怎么实现？

Reactor 作为反应器，上面同时挂载了成千上万个待唤醒的事件，这里使用了 mio 统一封装了操作系统的多路复用 API。在 Linux 中使用的是 Epoll[^3]，在 Mac 中使用的则是 Kqueue ^[1]

loop {
    // 轮询事件是否超时
    poll.poll(&events, timeout);
    for event in events.iter() {
        if (event.is_readable()) {
            for waker in event.readers.wakers {
                waker.wake();
            }
        }
        if (event.is_writeable()) {
            for waker in event.writers.wakers {
                waker.wake();
            }
        }
    }
}

一面 – 手写代码

1. 实现一个二分查找函数

#![allow(unused)]
fn main() {
use std::cmp::Ordering;

/// 给出一个从小到大排列的数组，请实现一个函数，用二分法把指定数组 x 的位置找出来。若 x
/// 不存在，则返回 -1. 若 x 存在多个，请返回 x 在数组中第一次出现的位置
fn find(arr: Vec<i32>, x: i32) -> i32 {
    let (mut left, mut right) = (0, arr.len() - 1);
    loop {
        if left > right {
            return -1;
        }

        let mut mid = (left + right) / 2;
        match arr[mid].cmp(&x) {
            // 记得要排除已经命中的元素！
            Ordering::Less => left = mid + 1,
            Ordering::Greater => right = mid - 1,
            Ordering::Equal => {
                while mid >= 1 && arr[mid - 1] == x {
                    mid -= 1;
                }

                return mid as i32;
            },
        }
    }
}

#[cfg(test)]
mod test {
    use super::*;

    #[test]
    fn should_return_minus1() {
        let arr = vec![1, 3, 5];
        let x = 2;

        assert_eq!(find(arr, x), -1);
    }

    #[test]
    fn should_return_mid() {
        let arr = vec![1, 3, 5, 7, 9, 10, 10];
        let x = 7;

        assert_eq!(find(arr, x), 3);
    }

    #[test]
    fn should_return_first() {
        let arr = vec![1, 3, 5, 7, 9, 10, 10];
        let x = 10;

        assert_eq!(find(arr, x), 5);
    }
}
}

Q: 请分析该函数的算法复杂度？
- A: 时间复杂度 $O (\log n)$ ，最坏情况下的事件复杂度是 $O (n)$
Q: 请优化这个算法？
- A：一个优化方法是 插值查找法 ，利用如下公式自动根据查找到的元素与目标的距离来修正下一次查找的区间范围，提高查找速度：

m i d = l e f t + \frac{k e y - a r r [l e f t]}{a r r [r i g h t] - k e y} (r i g h t - l e f t)

2. 镜像二叉树

请反转二叉树。如给出以下二叉树：

1
   /   \
  2     3
 / \   / \
4   5 6   7

反转为：

1
   /   \
  3     2
 / \   / \
7   6 5   4

递归解法：

#![allow(unused)]
fn main() {
use std::convert::Into;

struct Node {
    val: i32,
    left: NodeLink,
    right: NodeLink,
}

type NodeLink = Option<Box<Node>>;

fn construct_tree() -> Box<Node> {
    let l3left1 = Node {
        val: 4,
        left: None,
        right: None,
    };

    let l3right1 = Node {
        val: 5,
        left: None,
        right: None,
    };

    let l3left2 = Node {
        val: 6,
        left: None,
        right: None,
    };

    let l3right2 = Node {
        val: 7,
        left: None,
        right: None,
    };

    let l2left = Node {
        val: 2,
        left: Somenew(l3left1),
        right: Somenew(l3right1),
    };

    let l2right = Node {
        val: 3,
        left: Somenew(l3left2),
        right: Somenew(l3right2),
    };

    Box::new(Node {
        val: 1,
        left: Somenew(l2left),
        right: Somenew(l2right),
    })
}

fn construct_mirror() -> Box<Node> {
    let l3left1 = Node {
        val: 7,
        left: None,
        right: None,
    };

    let l3right1 = Node {
        val: 6,
        left: None,
        right: None,
    };

    let l3left2 = Node {
        val: 5,
        left: None,
        right: None,
    };

    let l3right2 = Node {
        val: 4,
        left: None,
        right: None,
    };

    let l2left = Node {
        val: 3,
        left: Somenew(l3left1),
        right: Somenew(l3right1),
    };

    let l2right = Node {
        val: 2,
        left: Somenew(l3left2),
        right: Somenew(l3right2),
    };

    Box::new(Node {
        val: 1,
        left: Somenew(l2left),
        right: Somenew(l2right),
    })
}

impl Into<Vec<i32>> for Box<Node> {
    fn into(mut self) -> Vec<i32> {
        let v_left: Vec<i32>;
        let v_right: Vec<i32>;
        v_left = if let Some(node) = self.left.take() {
            node.into()
        } else {
            Vec::new()
        };

        v_right = if let Some(node) = self.right.take() {
            node.into()
        } else {
            Vec::new()
        };

       let mut v = Vec::new();
       v.push(self.val);
       v.extend(v_left.into_iter());
       v.extend(v_right.into_iter());

       v
    }
}

fn mirror(root: &mut Node) {
    let (mut tmp_left, mut tmp_right) = None, NodeLink::None;

    if let Some(mut node) = root.left.take() {
        mirror(&mut node);
        tmp_left = Some(node);
    }

    if let Some(mut node) = root.right.take() {
        mirror(&mut node);
        tmp_right = Some(node);
    }

    root.left = tmp_right;
    root.right = tmp_left;
}

#[cfg(test)]
mod test {
    use super::*;

    #[test]
    fn should_mirrored() {
        let mut tree = construct_tree();
        let expect = construct_mirror();

        let mirror = mirror(&mut tree);
        assert_eq!(<Box<Node> as Into<Vec<i32>>>::into(tree), <Box<Node> as Into<Vec<i32>>>::into(expect));
    }
}
}

Q: 请优化这个算法？
- A：如果不用递归（因为递归会加深调用栈），可以使用 广度优先搜索算法 来自根向叶逐层反转左右子节点的指针，并将子节点的指针放入到队列中待进行处理。

Rust异步浅谈 – leaxoy ↩︎